package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {

    public List<String> generateParenthesis(int n) {
        List<String> retult = new ArrayList<>();
        bfs(retult,"",0,0,n);
        return retult;
    }

    /**
     *
     * @param retult
     * @param s 表示生成的字符串
     * @param l 表示生成的字符串中左括号有多少个
     * @param r 表示生成的字符串中右括号有多少个
     * @param n 表示括号对数
     */
    private void bfs(List<String> retult, String s, int l, int r, int n) {
        if(l > n || r > n || r > l) return ; // r > l就不可能成立 (()))(  就算后面再加(也不可能会符合条件
        if (l == n && r == n) retult.add(s);  // 如果没有满足这个 就会有l > n 或则 r > n之类的情况上面条件就会return掉
        bfs(retult,s+")",l,r+1,n);
        bfs(retult,s+"(",l+1,r,n);
    }
}
